
local	maze = {
			   { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			   { 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1},
			   { 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1},
			   { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1},
			   { 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1},
			   { 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1},
			   { 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1},
			   { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
			};

local openList = {}

local closelist = {}

-- local point = { parent = nil, f = 0, g= 0, h = 0, x = 0, y = 0 }

local function print_table(t)
	for k,v in pairs(t) do
		if type(v) == "table" then
			print(".....sub......")
			print_table(v)
		else
			print("key =" .. k .. ", val = " .. v)
		end

	end
end


local function print_res( point)
	print_table(point)

	print("--------------xianlu--------------")

	while point.parent do

		print("x = " .. point.x  .. ", y = " .. point.y)

		point = point.parent

	end

	print("x = " .. point.x  .. ", y = " .. point.y)

end



local function newPoint(x, y)

	return  { parent = nil, f = 0, g= 0, h = 0, x = x, y = y }

end


local function exists(tab, p)

	for i=1, #tab do

		if tab[i].x == p.x  and tab[i].y == p.y then
			return true
		end

	end

	return false


end


local function reach(x, y)
		return maze[x][y]  == 0

end


local function calcG(start, point)
	local g = 0
	if (math.abs(point.x- start.x) + math.abs(point.y - start.x)) == 2  then
		g = 14
	else
		g = 10
	end

	local pG = point.parent and point.parent.g or 0

	return pG + g

end

local function calcH( endPoint, point )

	local step = math.abs( point.x - endPoint.x) + math.abs( point.y - endPoint.y)
	return step * 10

end



function  findPath( startPoint, endPoint, isIgnoreCorner)
	table.insert(openList, startPoint)

	local tmpPoint = nil
	local roundPoints = nil
	local res = nil

	while #openList ~= 0 do
		tmpPoint = minPoint(openList)


		table.remove(openList, 1)
		table.insert(closelist, tmpPoint)

		roundPoints = surroundPoints(tmpPoint, isIgnoreCorner)

		for _,v in pairs(roundPoints) do

			if exists(openList, v) then
				foundPoint(tmpPoint, v)

			else
				notFoundPoint(tmpPoint, endPoint, v)
			end

			res = findPoint(openList, endPoint)
			if res then
				return res
			end


		end

	end

	return  findPoint(openList, endPoint)


end




function foundPoint( tmpStart, point )

		local g = calcG(tmpStart, point)

		if g < point.g then

			point.parent = tmpStart
			point.g = g
			point.f = point.g + point.h

		end


end

function notFoundPoint( tmpStart , endPoint, point)

	point.parent = tmpStart
	point.g = calcG(tmpStart, point)
	point.h = calcH(endPoint, point)
	point.f = point.g + point.h

	table.insert(openList, point)

end


function surroundPoints( point, isIgnoreCorner )

	local sporints = {}

	for x = point.x - 1, point.x + 1 do

		for y = point.y - 1, point.y + 1 do

			if canReach(point, x, y, isIgnoreCorner) then

				table.insert(sporints, newPoint(x, y))

			end

		end


	end

	return sporints

end



function canReach (start, x, y, isIgnoreCorner)

	if not reach(x, y) or exists(closelist, {x = x, y = y}) then
		return false
	else

		if math.abs(x - start.x) + math.abs(y - start.y) == 1 then
			return true
		else

			if reach( math.abs(x - 1), y) and reach ( x, math.abs(y - 1)) then
				return true
			else
				return isIgnoreCorner
			end

		end

	end



end


function minPoint(tab)

	table.sort(tab, function(a, b)
		return a.f < b.f
	end)



	return tab[1]

end

function findPoint( tab, point)

	for _, v in pairs(tab) do

		if v.x == point.x and v.y == point.y then

			return v;

		end

	end

	return nil

end



local sPoint = newPoint(2, 2)
local ePoint = newPoint(7, 11)


local lux = findPath(sPoint, ePoint, false)

print_res(lux)
